package com.sig.formes;

import java.util.ArrayList;
import java.util.Collections;

import android.util.Log;

/**
 * Cr???? par Florent, Kevin, TRT et Alex
 * Tous droits reserv??s, m??me celui de mort
 */

public class EarCutting {

	static private Point p;
	static private Point p0;
	static private Point p1;
	static private Point p2;

	static private Segment s;
	static private Segment cs0;
	static private Segment cs1;
	static private Segment cs2;

	static private float det0 = 0;
	static private float det1 = 0;

	static private Triangle t;

	static private int ear = 0;
	static private boolean breaker = false;
	static private boolean CW = true;


	static private ArrayList<Point> points = new ArrayList<Point>();
	static private ArrayList<Point> tmp = new ArrayList<Point>();
	static private ArrayList<Segment> segments = new ArrayList<Segment>();
	static private ArrayList<Triangle> triangles = new ArrayList<Triangle>();

	static public ArrayList<Triangle> cut(ArrayList<Point> pts , boolean performSelfIntersectionTest )
	{

		//if input array is too short
		if ( pts.size() < 3 ) {
			ArrayList<Triangle> oneTri = new ArrayList<Triangle>();
			oneTri.add(new Triangle( pts.get(0), pts.get(1), pts.get(2) ));
			return oneTri;
		}

		//working copy
		points = concat(pts);

		//builds a list of the polygon's segments
		buildSegments( points );

		//check for self intersection
		if ( performSelfIntersectionTest && selfIntersection() )
		{
			return new ArrayList<Triangle>();
		}

		// direction of the polygon
		CW = getDirection( points );

		//off we go
		process();

		return triangles;

	}

	static public ArrayList<Triangle> process()
	{
		//current ear being checked
		ear = 0;

		//some kind of safety belt...whatever
		breaker = false;

		triangles = new ArrayList<Triangle>();

		//working copy of the set of points
		tmp = concat(points);

		//recursive function that reduces the set of points until there's only one triangle left
		while ( tmp.size() > 2 )
		{
			tmp = earCut( tmp );
			if ( breaker )
			{
				return triangles;
			}
		}  
		return triangles;

	}


	static public ArrayList<Point> earCut(ArrayList<Point> pts )
	{

		Log.d("earCut","earCut("+pts.toString()+");");
		Log.d("earCut","{");
		//there's only one triangle
		if ( pts.size() < 3 )
		{
			triangles.add( new Triangle( pts.get(0), pts.get(1), pts.get(2) ) );
			return pts;
		}

		//current ear tip being processed
		ear = ( ear < 0 ) ? 0 : ear;



		//safety belt
		if ( ear >= pts.size() )
		{
			Log.d("earCut","p0 is out");
			breaker = true;
			return pts;
		}

		//safety belt
		if (  pts.get(ear) == null )
		{
			Log.d("earCut","p0 is null");
			breaker = true;
			return pts;
		}

		//creates a triangle

		p0 = pts.get(ear);

		p1 = pts.size() > ear+1 ? pts.get( ear + 1 ) : pts.get( 0 );

		p2 = pts.size() > ear+2 ? pts.get( ear + 2 ) : pts.get( 1 );

		Log.d("earCut","ear="+ear+", size="+pts.size()+" p0 : "+p0+"    p1 : "+p1+"    p2 : "+p2);

		t = new Triangle( p0, p1, p2 );

		//if the triangle contains one the remaining points: no good, skip to the next
		if ( triangleContainsPoints( t, pts ) )
		{
			ear++;
			return pts;
		}


		//is the segment inside the shape ?

		//those are temporary segments of the triangle being tested
		cs0.debut = cs2.fin = p0;
		cs1.debut = cs0.fin = p1;
		cs2.debut = cs1.fin = p2;

		//if that point is outside the shape, we'll have to find another one
		p = cs2.getCenter();

		det0 = determinant( cs0.debut, cs0.fin, p );
		det1 = determinant( cs1.debut, cs1.fin, p );

		//depending on the direction ( CW | CCW )
		//the point has to lie either to the left or to the right of both the other segments
		if ( ( CW && det0 > 0 && det1 > 0  ) || ( !CW && det0 < 0 && det1 < 0  ) )
		{
			//if not the case > skip to the next
			ear++;
			return pts;
		}

		// we have a valid triangle
		triangles.add( t );
		Log.d("earCut","splice");
		pts = splice(pts, ear + 1, 1 );//the point we were testing is p1
		ear--;

		Log.d("earCut","}");
		return pts;

	}

	//determines the polygon's direction: true-> CW | false -> CCW
	static private boolean getDirection(ArrayList<Point> tmp )
	{

		int i = tmp.size() - 1;

		p0 = tmp.get(i);
		p1 = tmp.size() < i-1 ? tmp.get( i + 1 ) : tmp.get(0);
		p2 = tmp.size() < i-2 ? tmp.get( i + 2 ) : tmp.get(1);

		cs0 = new Segment( p0, p1 );
		cs1 = new Segment( p1, p2 );
		cs2 = new Segment( p0, p2 );

		Point p = cs2.getCenter();

		Point ip;
		Point ep = new Point( p.x + 10000, p.y ,true);
		Segment cs = new Segment( p, ep );

		//if the count is odd, then the point is inside a shape
		//if it's even, then the point is outside
		int count = 0;
		Log.d("earCut","SEGMENT : "+segments.toString());
		for ( i = 0; i < segments.size(); i++ )
		{
			s = segments.get(i);
			ip = s.segmentIntersct( cs, true );
			if ( ip != null )
			{
				count++;
			}
		}
		Log.d("earCut","NBR intersect : "+count);

		//a little trick i don't get really but does crash the thing if not done:
		//if the first triangle contains one of the points, we reverse it.
		t = new Triangle( p0, p1, p2 );
		if ( count % 2 == 0 && !triangleContainsPoints( t, tmp ) ) {
			System.out.println("reverse");
			Collections.reverse(tmp);
		}

		det0 = determinant( cs0.debut, cs0.fin, p );
		det1 = determinant( cs1.debut, cs1.fin, p );

		return ( det0 < 0 && det1 < 0 );

	}

	//is the polygon simple?
	static public boolean selfIntersection()
	{
		Point ip;
		for(Segment s : segments )
		{
			for(Segment ss : segments )
			{
				if ( s != cs0 )
				{
					ip = s.segmentIntersct( ss, true );
					if ( ip != null
							&& !(s.debut.equals(ss.debut) || s.debut.equals(ss.fin) )
							&& !(s.fin.equals(ss.debut) || s.fin.equals(ss.fin) ))
					{
						return true;
					}
				}
			}
		}
		return false;
	}

	static public ArrayList<Segment> buildSegments(ArrayList<Point> poin )
	{
		segments = new ArrayList<Segment>();
		for (int i = 0; i < poin.size(); i++ )
		{

			p0 = poin.get(i);
			p1 = poin.size() > i+1 ? poin.get( i + 1 ) : poin.get(0);
			s = new Segment( p0, p1 );
			segments.add( s );

		}
		return segments;
	}

	static private boolean triangleContainsPoints(Triangle t,ArrayList<Point> pts )
	{
		int i;
		int PL = pts.size();
		for ( i = 0; i < PL; i++ )
		{
			p = pts.get(i);
			if ( !p.equals(p0) && !p.equals(p1) && !p.equals(p2)  )
			{
				if ( t.contains( p ) )
				{
					return true;
				}
			}
		}
		return false;
	}
	public static ArrayList<Point> splice(ArrayList<Point> lst, int start, int count)
	{
		for(int i=0;i<count; i++)
		{
			Log.d("earCut","remove : "+start);
			lst.remove(start);
		}
		return lst;
	}
	public static ArrayList<Point> concat(ArrayList<Point> lst)
	{
		ArrayList<Point> newArray = new ArrayList<Point>();
		newArray.addAll(lst);
		return newArray;
	}
	static public float determinant(Point p0,Point p1,Point p2)
	{
		return ( ( p0.x-p1.x )*( p2.y - p1.y ) ) - ( ( p2.x-p1.x )*( p0.y-p1.y ) );
	}
}